package com.ly.sort;


import java.util.Arrays;

public class QuickSort implements Sort{

    @Override
    public int[] sort(int[] arr) {
        QuickSort(arr, 0, arr.length - 1);
        return arr;
    }

    /**
     * 快速排序方法
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static void QuickSort(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end > array.length || start >= end) return ;
        int privot = array[start];
        int left = start;
        int right = end;
        while(left < right){
            while(left < right && array[right] > privot){
                right --;
            }
            if(left < right){
                array[left++] = array[right];
            }

            while(left < right && array[left] < privot){
                left ++;
            }
            if(left < right){
                array[right--] = array[left];
            }
        }
        array[left] = privot;
        QuickSort(array, start, left - 1);
        QuickSort(array, left + 1, end);
//        return left;
    }

}
